package puzzle.puzzleup2007;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import astudy.util.AdvMath;

/**
 * -2007 Problem 11-
 * You have cards numbered from 1 to 20. First you will 
 * put them in order, and then you will shuffle them randomly. 
 * You will examine the distribution of cards before and after 
 * shuffling in order to determine the operation. Your aim is 
 * to get the initial order, repeating the same operation. 
 * What is the maximum number of shuffles necessary in order to 
 * reach the initial order?
 * 
 * If the question was asked for four cards, the answer would 
 * be 4. As an example, with four cards A, B, C, D, and beginning 
 * with the order ABCD, let us assume we get the order CADB in the 
 * first shuffle. Then initial: ABCD, first shuffling: CADB, second 
 * shuffling: DCBA, third shuffling: BDAC and fourth shuffling: ABCD.
 * 
 * -Solution-
 * �����������֪������ʵ������Ҫ�󣬽�20��ֺ󣬲�������С����������Ƕ��٣�
 */
public class Cards {

	public static void main(String[] argv) {
		
		BigInteger n = BigInteger.valueOf(14);;
		List<List<BigInteger>> ll = p(n, n);
		BigInteger max = BigInteger.ZERO;
		List<List<BigInteger>> ps = new ArrayList<List<BigInteger>>();
		BigInteger lcd = BigInteger.ZERO;
		for (List<BigInteger> l : ll) {
			lcd = AdvMath.lcd(l);
			
			if (lcd.compareTo(max) > 0) {
				max = lcd;
				ps.clear();
				ps.add(l);
			} else if (lcd == max) {
				ps.add(l);
			}
		}
		System.out.println("max: " + max);
		for (List<BigInteger> p : ps) {
			for (int i = 0; i < p.size(); i ++) {
				if (p.get(i) == null) {
					p.remove(i);
				}
			}
			System.out.println(AdvMath.combine(p.toArray(new BigInteger[p.size()])) + "\t: " + p);
		}
	}

	/**
	 * ���n����������ÿ�������m�����в��
	 * @param n
	 * @param m
	 * @return
	 */
	private static List<List<BigInteger>> p(BigInteger n, BigInteger m) {

		if ((n.compareTo(BigInteger.ONE) < 0) || (m.compareTo(BigInteger.ONE) < 0)) {
			return null;  
		}
		if (n.compareTo(BigInteger.ONE) == 0) {
			List<List<BigInteger>> aa = new ArrayList<List<BigInteger>>();
			List<BigInteger> a = new ArrayList<BigInteger>();
			a.add(BigInteger.ONE);
			aa.add(a);
			return aa;
		}
		if (m.compareTo(BigInteger.ONE) == 0) {
			List<List<BigInteger>> aa = new ArrayList<List<BigInteger>>();
			List<BigInteger> a = new ArrayList<BigInteger>();
			BigInteger i = BigInteger.ZERO;
			while (i.compareTo(n) < 0) {
				a.add(BigInteger.ONE);
				i = i.add(BigInteger.ONE);
			}
			aa.add(a);
			return aa;
		}
		if (m.compareTo(n) > 0) {
			return p(n,n);  
		}
		if (n == m) {
			List<BigInteger> a = new ArrayList<BigInteger>();
			a.add(m);
			List<List<BigInteger>> aa = p(n,m.subtract(BigInteger.ONE));
			if (aa == null) {
				aa = new ArrayList<List<BigInteger>>();
			}
			aa.add(a);
			return aa;
		}
		
		List<List<BigInteger>> aa1 = p(n,m.subtract(BigInteger.ONE));
		List<List<BigInteger>> aa2 = p(n.subtract(m),m);
		if (aa2 != null) {
			for (int i = 0; i < aa2.size(); i ++) {
				aa2.get(i).add(m);
			}
		}
		if (aa1 == null) {
			return aa2;
		} else if (aa2 == null) {
			return aa1;
		} else {
			aa1.addAll(aa2);
			return aa1;
		}
	}
}